1. Field of the Invention
The present invention relates to implementing error correcting codes and a network coding scheme within a communications network.
More specifically, the invention pertains to the implementing of such error correcting codes and network coding in the context of the transmission of data packets in a meshed communication network.
2. Description of the Related Art
Certain wireless communication networks jointly use an error correcting code, for example of an LDPC (Low Density Parity Check Code) type, as well as network coding scheme (network coding scheme corresponds to the packet-combining operation performed by the nodes of the network).
The present invention is not limited to this particular field of application but can be used in any type of network jointly using a linear error correcting code as well as network coding scheme.
In a wireless meshed communication network, the time division multiple access (TDMA) mode is often used to enable the nodes included in said network to transmit data (through data packets sent within a superframe). The nodes send data according to a common modulation scheme, sending packets during the time slot assigned to them. It may be noted that, depending on the modulation scheme used (for example one of the following schemes: BPSK (binary phase-shift keying), QPSK (quadrature phase-shift keying), 8PSK, 16QAM (quadrature amplitude modulation), etc. . . . ) within the network, it is possible, in determining the ratio Eb/No of the system (corresponding to the ratio of the energy per bit (Eb) to the spectral density of the noise (No)), to know the bit error rate or binary error rate (BER) on an additive white Gaussian noise channel (this type of channel provides a fairly good model of the real links or paths existing between the nodes of the network). For example, when the QPSK modulation scheme is used, the following relationship is verified: BER=(½) erfc (Eb/No) where erfc is the complementary error function. It may be recalled that the signal-to-noise ratio (SNR) also denoted as S/N is equal to (n*Eb)/(No*B) where B is the bandwidth of the signal and N is the number of bits present in the signal S. For example, here below in the description, we use only the SNR because it is easier to estimate.
Thus, by estimating the SNR of a modulation scheme, it is possible to predict the BER. It must be noted that the smaller the SNR, the greater the BER and therefore the greater the likelihood that the packet sent by the nodes will comprise many errors. In this example, it is worthwhile to use error correcting codes (to encode packets at the level of a source node) having high corrective power as well as a network coding scheme which, as a function of spatial configuration, makes it possible to convey a greater number of redundant packets to the destination node.
It may be advantageous especially (but not exclusively) in this type of network to use an LDPC code also called a Gallagher code which is a linear block code and can perform better than a turbo-code in certain conditions. Since the LDPC codes are linear codes, they are defined on the basis of their control matrix H which is generally not a systematic matrix. It may be recalled that there are two classes of LDPC codes: regular LDPC codes and irregular LDPC codes. An LDPC code is said to be regular in the particular case where the control matrix H contains a constant number of 1s in each row and a constant number of 1s in each column. If an LDPC code does not verify this property, it is said to be irregular. It turns out that it is the irregular LDPC codes that seem to have the best performance in binary-input symmetric-output memoryless channels, binary erasure channels and additive white Gaussian noise (noise modeled by a generalized Gaussian distribution) channels. Now these types of channels model existing communications links in a wireless meshed network. Thus, by using these special irregular LDPC codes in a wireless meshed communications network, Shannon's limit on these channels can be approached.
The decoding of an LDPC code is done on the same principle as that of a turbo-code, by an iterative algorithm called a belief-propagation algorithm well known to those skilled in the art.
The fact of using a network coding scheme jointly with the use of an LDPC encoding enables correction of a greater number of errors in the received packets (through packet redundancy information) than in the case of the use of only one protection technique. In particular, when the binary error rate (BER) on certain links increases, the synergy between these codes is remarkable.
Indeed, through the use of network coding scheme, a relay node may simply re-transmit a packet, create a copy of the packet after having demodulated it, correct the errors and retrieve the original payload information or else combine several packets to create a combined packet which will be transmitted. The repetition prevents a certain number of packet losses for the destination node which could result for example from the concealment of the direct line between senders and receivers in a wireless network.
It is for this reason that, in the prior art, depending on the pre-designed properties of a physical channel, those skilled in the art choose to implant a given modulation scheme for the system as well as a particular LDPC code (for example) in the nodes of the network as well as a network coding scheme, once and for all, and for the entire lifetime of the nodes.
More specifically, in a wireless communications network subjected to numerous shadowing phenomena, those skilled in the art will use a modulation scheme providing a low bit rate (thus fewer bits will be lost during interference) and error correcting codes that have high corrective power (i.e. approaching Shannon's limit) but are generally complex in terms of resources used (such as for example irregular LDPC codes). They will also use a network coding scheme which is itself an error correcting code (for example a distributed correcting code) thus creating a product code.
By contrast, in a wireless communications network subjected to little shadowing, those skilled in the art will use a modulation scheme providing a high bit rate and error correcting codes that have a lower corrective power (i.e. require fewer resources than in the previous example) and are above all less complex in their implementing (for example Reed Solomon codes). In addition they could use a network coding scheme which is not an error correcting code.
However, these approaches are not optimal when the communication network undergoes interference in varying degrees (in duration and intensity) and in a random manner.
Furthermore, another drawback of this classic technique is that it implements a sometimes excessive use of available resources in the source node, as well as in the relay nodes and in the destination node.